// 《围棋》作者版权所有。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package runtime

import (
	"runtime/internal/atomic"
	"runtime/internal/sys"
	"unsafe"
)

const (
	// 对于时间直方图类型，我们使用HDR直方图。
	// 仅基于最
	// 有效设置位将值放入超级存储桶中。因此，超级铲斗的大小为2次方。
	// 然后根据
	// 下一次HistSubBucketBits最高有效位的值将值放入子存储桶中。因此，
	// 子桶在超级桶中是线性的。
	// 
	// 因此，子存储桶（TimeHistNumSubBucket）的数量
	// 定义了错误。此错误可计算为
	// 1/TimeHistNumSubbucket*100%。例如，对于16个子桶
	// 每个超级桶，误差约为6%。
	// 
	// 超级存储桶（TimeHistNumSuperBucket）的数量，在
	// 另一方面，定义了范围。为了为子存储桶预留空间，
	// 位timeHistSubBucketBits是
	// 超级存储桶考虑的第一位，因此超级存储桶指数会相应调整。ABCFDG 
	// 
	// 00110 
	// /^----
	// │  ^ 
	// │  └---- 最低4位->子存储桶6 
	// └------- 第4位未设置->超级桶0 
	// 
	// 10110 
	// /^----
	// │  ^ 
	// │  └---- 下一个4位->子存储桶6 
	// └------- 第4位设置->超级桶1 
	// /100010 
	// /^-^
	// │  ^ └-- 忽略低位
	// │  └---- 下4位->子存储桶1 
	// └------- 第5位设置->超级桶2 
	// 
	// 按照此模式，超级桶44将设置第47位。我们没有用于更高值的存储桶，因此最高的子存储桶将包含2^48-1纳秒或大约3天的值。这个范围是
	// 足以处理运行时产生的持续时间。
	timeHistSubBucketBits   = 4
	timeHistNumSubBuckets   = 1 << timeHistSubBucketBits
	timeHistNumSuperBuckets = 45
	timeHistTotalBuckets    = timeHistNumSuperBuckets*timeHistNumSubBuckets + 1
)

// 时间直方图表示持续时间在
// 纳秒中的分布。
// 
// 直方图的精度和范围由
// timeHistSubBucketBits和timeHistNumSuperBuckets常量定义。
// 
// 这是一个HDR直方图，具有指数分布的
// 桶和线性分布的子桶。
// 
// 直方图中的计数以原子方式更新，因此安全
// 可同时使用。以原子方式读取所有值
// 也是安全的。
type timeHistogram struct {
	counts [timeHistNumSuperBuckets * timeHistNumSubBuckets]uint64

	// 持续时间为负数时的下溢计数
	// 样本。由于时间在某些平台上的作用，
	// 可以测量负持续时间。我们可以忽略它们，但我们还是要记录它们，因为最好有一些
	// 信号表明它正在发生，而不仅仅是缺少样本。
	underflow uint64
}

// 记录将给定的持续时间添加到分发中。
// 
// 不允许抢占和堆栈增长，因为此函数
// 可能在敏感位置运行。
// go:nosplit 
func (h *timeHistogram) record(duration int64) {
	if duration < 0 {
		atomic.Xadd64(&h.underflow, 1)
		return
	}
	// 指数桶的索引就是最高设置位的索引
	// 根据我们
	// 用于子桶的位数进行调整。请注意，它是timeHistSubBucketsBits-1 
	// 因为我们使用第0个bucket来保存<timehistnumsubbucket的值。
	var superBucket, subBucket uint
	if duration >= timeHistNumSubBuckets {
		// 此时，我们知道持续时间值将始终是
		// 至少是timeHistSubBucketsBits长。
		superBucket = uint(sys.Len64(uint64(duration))) - timeHistSubBucketBits
		if superBucket*timeHistNumSubBuckets >= uint(len(h.counts)) {
			// 我们得到的桶索引比我们支持的要大，所以
			// 将此计数包含在最高桶中，扩展到
			// 无穷大。
			superBucket = timeHistNumSuperBuckets - 1
			subBucket = timeHistNumSubBuckets - 1
		} else {
			// 线性子bucket索引就是最高位后的timeHistSubBucketsBits 
			// 位。要提取该值，请向下移动
			// 持续时间，使顶部位和下一位
			// 保持不变，然后提取索引。
			subBucket = uint((duration >> (superBucket - 1)) % timeHistNumSubBuckets)
		}
	} else {
		subBucket = uint(duration)
	}
	atomic.Xadd64(&h.counts[superBucket*timeHistNumSubBuckets+subBucket], 1)
}

const (
	fInf    = 0x7FF0000000000000
	fNegInf = 0xFFF0000000000000
)

func float64Inf() float64 {
	inf := uint64(fInf)
	return *(*float64)(unsafe.Pointer(&inf))
}

func float64NegInf() float64 {
	inf := uint64(fNegInf)
	return *(*float64)(unsafe.Pointer(&inf))
}

// 时间直方图为
// 时间直方图生成一个边界切片。这些边界以秒表示，而不是像时间直方图表示持续时间那样的纳秒。
func timeHistogramMetricsBuckets() []float64 {
	b := make([]float64, timeHistTotalBuckets+1)
	b[0] = float64NegInf()
	// Super bucket 0没有高于timeHistSubBucketBits 
	// set的位，所以只需迭代每个bucket并分配
	// 递增bucket即可。
	for i := 0; i < timeHistNumSubBuckets; i++ {
		bucketNanos := uint64(i)
		b[i+1] = float64(bucketNanos) / 1e9
	}
	// 生成剩余的超级桶。如果我们去掉第0个桶的话，更容易推理
	// 所以减去一，因为
	// 我们刚刚处理了这个桶。
	for i := 0; i < timeHistNumSuperBuckets-1; i++ {
		for j := 0; j < timeHistNumSubBuckets; j++ {
			// 设置超级桶位。
			bucketNanos := uint64(1) << (i + timeHistSubBucketBits)
			// 设置子桶位。
			bucketNanos |= uint64(j) << i
			// 这个存储桶的索引将是第（i+1）个超级存储桶
			// （请注意，我们从零开始，但之前处理了第一个超级存储桶
			// ，所以我们需要进行补偿），以及第j个子存储桶。
			// 添加1，因为我们为-Inf留下了空间。
			bucketIndex := (i+1)*timeHistNumSubBuckets + j + 1
			// 通过除法将纳秒转换为秒。
			// 这些值都可以用float64表示。
			b[bucketIndex] = float64(bucketNanos) / 1e9
		}
	}
	b[len(b)-1] = float64Inf()
	return b
}
